// 有一堆石头，每块石头的重量都是正整数。

// 每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。
// 假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

// 如果 x == y，那么两块石头都会被完全粉碎；
// 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
// 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

const lastStoneWeight = function (stones: number[]): number {
    while (stones.length > 1) {
        stones.sort((a, b) => a - b); // 对原数组升序排序
        const lastIndex: number = stones.length - 1;
        // 判断情况：头元素可能大于或等于二位元素
        if (stones[lastIndex] > stones[lastIndex - 1]) {
            stones[lastIndex - 1] = stones[lastIndex] - stones[lastIndex - 1];
        } else {
            stones.pop();
        }
        stones.pop();
    }
    return stones.length > 0 ? stones[0] : 0;
};

lastStoneWeight(
    [2, 7, 4, 1, 8, 1])


// 这道题这里使用了比较粗暴的解法
// 即：不断地使用快速排序来模拟题目中的过程
// 从算法设计的角度没有太多技术含量可言
// 唯一需要注意的是这里对数组采取的是当作栈来处理
// 即多使用Pop方法而不是shift方法，这在一定程度上提高了少许的性能。